package wtx.geek;

import java.util.*;
import java.util.Random;


/**
 * Given a value and a binary search tree.
Print all the paths(if there exists more than one) which sum up to that value. 
It can be any path in the tree. It doesn't have to be from the root.

-- hints from wentongxin:
for each node, find the upper and lower bound of the left/right subtree,
do a binary search base on the range
 
 **/

public class Solution {
  public static int[] findLongestEqualSubrange(int[] array) {
    final int len = array.length;
    int[] array2 = new int[len+1];
    array2[0] = 0;
    for (int i = 1; i <= len; ++i) {
      array2[i] = array2[i-1] + (array[i-1] == 0 ? 1 : -1);
    }
    Map<Integer, Integer> firstOccur = new HashMap<>(),
            lastOccur = new HashMap<>();
    int maxLen = 0;
    int left = -1, right = -1;
    Set<Integer> usedEle = new HashSet<>();
    for (int i = 0; i <= len; ++i) {
      int ele = array2[i];
      firstOccur.putIfAbsent(ele, i);
      int ele2 = array2[len - i];
      lastOccur.putIfAbsent(ele2, len - i);
    }

    for (int i = 0; i <= len; ++i) {
      int ele = array2[i];
      if (!usedEle.contains(ele) && lastOccur.containsKey(ele)) {
        int lenRange = lastOccur.get(ele) - firstOccur.get(ele);
        if (lenRange > maxLen) {
          maxLen = lenRange;
          left = i;
          right = lastOccur.get(ele);
        }
        usedEle.add(ele);
      }
      if (maxLen > len-i) {
        break;
      }
    }
    int[] array_out = new int[right-left];
    for (int i = 0; i < maxLen; ++i) {
      array_out[i] = array[i+left];
    }
    return array_out;
  }

  public static int[] findLongestEqualSubrangeNotWork(int[] array) {
    /**
     首先统计整个字符串的所有元素和sum，如果2*sum == len，则返回[0, len-1]
     如果2*sum < len，说明0多，需要找左右2边为0的删掉；如果两边都是1, 寻找左右2边距离0最近的一边进行删除
     另外一边和0的距离可以保存下来，方便下次使用。
     如果2*sum > len, 说明1多。采用和上面类似的方式进行处理
     */
    int len = array.length;
    int ones = 0, zeros;
    for (int i = 0; i < len; ++i) {
      ones += array[i];
    }
    zeros = len - ones;
    if (ones == zeros) {
      return array;
    }
    int leftOnes = 0, rightOnes = 0, leftZeros = 0, rightZeros = 0;
    int i = 0, j = len-1;
    while (i < len && j >= 0 && ones != zeros) {
      if (ones > zeros) {
        // remove extra ones
        if (array[i] == 1) {
          ++i;
          --ones;
        } else if (array[j] == 1) {
          --j;
          --ones;
        } else {
          if (leftZeros == 0) {
            while(i < j && array[i+leftZeros] == 0) {
              ++leftZeros;
            }
          }
          if (rightZeros == 0) {
            while(i < j && array[j-rightZeros] == 0) {
              ++rightZeros;
            }
          }
          if (leftZeros < rightZeros) {
            i += leftZeros;
            zeros -= leftZeros;
            leftZeros = 0;
          } else {
            j -= rightZeros;
            zeros -= rightZeros;
            rightZeros = 0;
          }
        }
      } else {
        // remove extra zeros
        if (array[i] == 0) {
          ++i;
          --zeros;
        } else if (array[j] == 0) {
          --j;
          --zeros;
        } else {
          if (leftOnes == 0) {
            while(i < j && array[i+leftOnes] == 1) {
              ++leftOnes;
            }
          }
          if (rightOnes == 0) {
            while(i < j && array[j-rightOnes] == 1) {
              ++rightOnes;
            }
          }
          if (leftOnes < rightOnes) {
            i += leftOnes;
            ones -= leftOnes;
            leftOnes = 0;
          } else {
            j -= rightOnes;
            ones -= rightOnes;
            rightOnes = 0;
          }
        }
      }
    }
    if (ones != zeros) {
      return null;
    }
    int k = 0;
    int[] ret = new int[j-i+1];
    for (; i <= j; ++i) {
      ret[k++] = array[i];
    }
    return ret;
  }

  public static void main(String[] args) {
    int[] array = {0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0};
    int[] range = findLongestEqualSubrange(array);
    StringJoiner sj = new StringJoiner(", ");
    for (int i = 0; i < range.length; ++i) {
      sj.add(String.valueOf(range[i]));
    }
    System.out.println("longest zeros-ones range: " + sj.toString());
  }
}
